package style.zcyLeetCode.a_0005_二叉树;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 找出最低的公共祖先
 */
public class LowestCommonAncestor {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    /**
     * 解法一：晦涩难懂
     *  1、o1与o2是祖先关系
     *  2、o1与o2不是祖先关系
     */
    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestAncestor(head.left, o1, o2);
        Node right = lowestAncestor(head.right, o1, o2);
        // 说明head是最低的公共祖先
        if (left != null && right != null) {
            return head;
        }
        // 左右 两棵树，并不都有返回值
        return left != null ? left : right;
    }


    /**
     *  解法二：
         *  1、先把所有的父子关系存在map中
         *  2、把o1的所有父节点存在set中
         *  3、判断o2的往上的节点是否在set中
     */
    public static Node lca(Node head, Node o1, Node o2) {
        HashMap<Node, Node> fatherMap = new HashMap<>();
        // 先把所有的父子关系存在map中
        fatherMap.put(head, head);
        process(head, fatherMap);

        // 把o1所有的父节点存在set1中
        HashSet<Node> set1 = new HashSet<>();

        Node cur = o1;
        while (cur != fatherMap.get(cur)) {
            set1.add(cur);
            cur = fatherMap.get(cur);
        }
        set1.add(head);

        // 判断 set1 判断o2的所有父节点是否在set1中，返回的是
        Node curr = o2;
        while (! set1.contains(fatherMap.get(curr))) {
            curr = fatherMap.get(curr);
        }
        return fatherMap.get(curr);
    }

    public static void process(Node head, HashMap<Node, Node> fatherMap) {
        if (head == null) {
            return;
        }
        fatherMap.put(head.left, head);
        fatherMap.put(head.right, head);
        process(head.left, fatherMap);
        process(head.right, fatherMap);
    }



    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.right.right.left = new Node(8);
        System.out.println("===============");

        Node o1 = head.left.right;
        Node o2 = head.right.left;

        System.out.println("o1 : " + o1.value);
        System.out.println("o2 : " + o2.value);
        System.out.println("ancestor : " + lowestAncestor(head, o1, o2).value);
        System.out.println("===============");
        System.out.println("ancestor1 : "+lca(head, o1, o2).value);
    }


}
